package cg.studio.algorithm.sort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class RadixSorter implements NumericSorter<Number>
{
  /**
   * the data of Radix sorter can't negative.
   * use 0xFF buckets
   */
  public List<Number> sort( List<Number> orgDatas )
  {
    if( orgDatas == null || orgDatas.isEmpty() )
      return orgDatas;
    
    //clone datas to a ArrayList for preventing the sort.
    ArrayList<Number> datas = new ArrayList<Number>( orgDatas.size() );
    for( Number data : orgDatas )
    {
      datas.add( data );
    }

    Map< Integer, List<Number> > buckets = new HashMap< Integer, List<Number> >();
    
    int dataBytes = getDataByets( datas );
    //which byte is calculating? 
    final int eachShift = 4;
    final int maxBucketValue = 0x0F;
    final int shiftCount = dataBytes*2;
    
    for( int shiftIndex = 0; ; ++shiftIndex )
    {
      for( Number data : datas )
      {
        int bucketValue = getBucketValue( data, eachShift, shiftIndex );
        List<Number> bucketList = buckets.get( bucketValue );
        if( bucketList == null )
          bucketList = new LinkedList<Number>();
        buckets.put( Integer.valueOf( bucketValue ), bucketList );
        bucketList.add( data );
      }
      
      //regenerate the list from buckets
      datas.clear();
      Set<Integer> keys = buckets.keySet();
      keys = Collections.checkedSet( keys, Integer.class );
      for( int key : keys )
      {
        List<Number> curBucket = buckets.get( key );
        if( curBucket != null )
          datas.addAll( curBucket );
      }
      
      if( shiftIndex >= shiftCount )
        return datas;
      
      buckets.clear();
    }
    
  }
  
  /**
   * get how much bytes for this type of data
   * @return
   */
  public int getDataByets( Collection<Number> datas )
  {
    for( Number data : datas )
    {
      if( data instanceof Long )
        return Long.SIZE/Byte.SIZE;
      else if( data instanceof Integer )
        return Integer.SIZE/Byte.SIZE;
      else
        throw new IllegalArgumentException( "Invalid data type: " + data.getClass() );
    }
    throw new IllegalArgumentException( "Invalid data type." );
  }
  


  /**
   * 
   * @param data
   * @param eachShift
   * @param shiftIndex
   * @return
   */
  public int getBucketValue( Number data, int eachShift, int shiftIndex )
  {
    long longValue;
    if( data instanceof Long )
      longValue = (long)(Long)data;
    else
      longValue = (long)(Integer)data;
    
    longValue >>= eachShift*shiftIndex;
    return (int)(longValue & 0X0F );
  }
  
}
